package org.leetcode.middle.leetcode718;

import java.util.Arrays;

public class Solution2 {

    public static void main(String[] args) {
        int [] num1 ={1,2,3,2,1};
        int [] num2 ={3,2,1,4,7};

        int maxLength = findLength(num1, num2);
        System.out.println("maxLength is "+ maxLength);
    }

    public static int findLength(int[] nums1, int[] nums2) {

        int n1 = nums1.length;
        int n2 = nums2.length;

        //nums1[i-1]为结尾和以nums2[j-1]为结尾的最长公共子数组的长度
        //nums1[i-1]和nums2[j-1]相等表示子数组是连续的，在前一个基础上加1
        //nums1[i-1]和nums2[j-1]不相等表示子数组不连续，断开了，设置为0
        int[][] dp = new int[n1 + 1][n2 + 1];

        int maxLength = 0;

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }


        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2 ; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }

        return maxLength;
    }
}
